home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / asmutil / asm_n_z.zip / SIEVE86.ASM < prev    next >
Assembly Source File  |  1987-05-01  |  7KB  |  303 lines
  1.     title    'Eratosthenes Sieve for 80x86 Real Mode'
  2.     name    sieve
  3.     page    50,132
  4.  
  5. ;
  6. ; Eratosthenes Sieve for 80x86 Real Mode
  7. ; Implemented by Ray Duncan, April 1987
  8. ; After Gilbreath, Byte September 1981, and January 1983
  9. ;
  10.  
  11. niter    equ     100              ; number of iterations
  12. asize   equ     8190            ; size of array "flags"
  13.  
  14. cr    equ    0dh            ; ASCII carriage return
  15. lf    equ    0ah            ; ASCII line feed
  16.  
  17. stdin    equ     0            ; handle for standard input
  18. stdout    equ    1            ; handle for standard output
  19.  
  20.  
  21. _TEXT    segment para public 'CODE'
  22.  
  23.     assume cs:_TEXT,ds:_DATA,es:_DATA
  24.  
  25. sieve    proc    near
  26.  
  27.     mov    ax,seg _DATA
  28.     mov    ds,ax
  29.     mov    es,ax
  30.  
  31.     mov    dx,0            ; convert number of iterations
  32.     mov    ax,niter
  33.     mov    cx,10
  34.     mov    si,offset msg1a+3
  35.     call    binasc
  36.  
  37.     mov    dx,offset msg1        ; display message
  38.     mov    cx,msg1_len        ; "Starting N iterations of Sieve"
  39.     call    pmsg
  40.  
  41.     call    getmsec            ; get current time in msec
  42.     push    dx            ; and save it ...
  43.     push    ax
  44.  
  45.         mov     counter,niter        ; initialize iterations counter
  46.  
  47. sieve1:                    ; a sieve iteration starts here...
  48.     mov    di,offset flags        ; initialize flags array
  49.     mov    cx,asize        ; to all bytes = TRUE
  50.     mov    al,1
  51.     cld
  52.     rep stosb
  53.  
  54.      xor    si,si            ; SI=  index to flags array
  55.     xor    di,di            ; DI = primes counter
  56.  
  57. sieve2:                     ; main loop of sieve
  58.         test    byte ptr flags[si],1    ; is this a prime?
  59.     jnz    short sieve4        ; jump if prime
  60.  
  61. sieve3:    inc     si            ; bump to next slot in "flags"
  62.         cmp     si,asize        ; are we done?
  63.         jle    sieve2            ; jump to test another
  64.  
  65.      dec     word ptr counter    ; more iterations?
  66.         jnz     sieve1            ; jump, another iteration needed
  67.     jmp    sieve7
  68.  
  69. sieve4:                    ; prime found, zap its multiples
  70.     mov    bx,si            ; copy i
  71.      mov     dx,bx             ; DX = prime = i + i + 3
  72.         add    dx,dx
  73.         add     dx,3
  74.     xor    al,al
  75.     jmp    short sieve6
  76.  
  77. sieve5:    mov    byte ptr flags[bx],al    ; zero this multiple
  78.  
  79. sieve6:    add     bx,dx            ; find next multiple of prime
  80.         cmp     bx,asize        ; have we exhausted the array?
  81.         jle    sieve5            ; not yet, zap it
  82.     inc     di            ; count primes and try next
  83.     jmp    sieve3
  84.  
  85. sieve7:                    ; done with all iterations...
  86.     call    getmsec            ; get current time
  87.     push    dx            ; and save it...
  88.     push    ax
  89.  
  90.     mov    ax,di            ; convert number of primes
  91.     mov    dx,0
  92.     mov    cx,10
  93.     mov    si,offset msg2a+4
  94.     call    binasc
  95.  
  96.     mov    dx,offset msg2        ; display "Number of primes: "
  97.     mov    cx,msg2_len
  98.     call    pmsg
  99.  
  100.     pop    ax            ; stop time:  low word
  101.     pop    dx            ;             high word
  102.  
  103.     pop    bx            ; start time: low word
  104.     pop    cx            ;             high word
  105.  
  106.     sub    ax,bx            ; DX:AX = stop - start 
  107.     sbb    dx,cx
  108.  
  109.     mov    cx,niter        ; divide by number of iterations
  110.     idiv    cx
  111.  
  112.     mov    dx,0            ; convert msec to ASCII
  113.     mov    cx,10
  114.     mov    si,offset msg3a+4
  115.     call    binasc
  116.  
  117.     mov    dx,offset msg3        ; display "Elapsed time:"
  118.     mov    cx,msg3_len
  119.     call    pmsg
  120.  
  121.      mov     ax,04C00h        ; exit to DOS with
  122.         int     21H            ; return code = 0
  123.  
  124. sieve    endp
  125.  
  126.  
  127. getmsec    proc    near            ; DX:AX := current time in msec.
  128.  
  129.     mov    ah,2ch            ; read time from MS-DOS    
  130.     int    21h
  131.     push    dx            ; save seconds, hundredths
  132.     mov    al,ch            ; AX := hours
  133.     cbw
  134.     mov    bx,60            ; hours -> minutes
  135.     imul    bx
  136.     xor    ch,ch            ; isolate system minutes
  137.     add    ax,cx            ; and find total minutes
  138.     mov    bx,60            ; minutes -> seconds
  139.     imul    bx
  140.     pop    cx            ; recover seconds, hundredths
  141.     mov    bl,ch            ; get seconds
  142.     xor    bh,bh
  143.     add    ax,bx            ; find total seconds
  144.     adc    dx,0            ; carry if necessary
  145.     xor    ch,ch            ; save centisec.
  146.     mov    bp,cx
  147.                     ; total seconds * 100 the hard way
  148.     mov    bx,ax            ; double multiply * 10 
  149.     mov    cx,dx
  150.     add    ax,ax            ; * 2
  151.     adc    dx,dx
  152.     add    ax,ax            ; * 4
  153.     adc    dx,dx
  154.     add    ax,bx            ; * 5
  155.     adc    dx,cx
  156.     add    ax,ax            ; * 10
  157.     adc    dx,dx
  158.  
  159.     mov    bx,ax            ; double multiply * 10 
  160.     mov    cx,dx
  161.     add    ax,ax            ; * 2
  162.     adc    dx,dx
  163.     add    ax,ax            ; * 4
  164.     adc    dx,dx
  165.     add    ax,bx            ; * 5
  166.     adc    dx,cx
  167.     add    ax,ax            ; * 10
  168.     adc    dx,dx
  169.  
  170.     add    ax,bp            ; add in hundredths of seconds
  171.     adc    dx,0
  172.                     ; now convert total to msec.
  173.     mov    bx,ax            ; double multiply * 10 
  174.     mov    cx,dx
  175.     add    ax,ax            ; * 2
  176.     adc    dx,dx
  177.     add    ax,ax            ; * 4
  178.     adc    dx,dx
  179.     add    ax,bx            ; * 5
  180.     adc    dx,cx
  181.     add    ax,ax            ; * 10
  182.     adc    dx,dx
  183.  
  184.     ret                ; return DX:AX = msec.
  185.  
  186. getmsec    endp
  187.  
  188.  
  189. ;
  190. ; BINASC: Convert 32 bit binary value to ASCII string.
  191. ;
  192. ; Call with  DX:AX = signed 32 bit value
  193. ;         CX    = radix
  194. ;            SI    = last byte of area to store resulting string
  195. ;                 (make sure enough room is available to store
  196. ;              the string in the radix you have selected.)
  197. ;
  198. ; Destroys AX, BX, CX, DX, and SI.
  199. ;
  200. binasc     proc    near            ; convert DX:AX to ASCII.
  201.  
  202.     mov    byte ptr [si],'0'     ; force storage of at least 1 digit.
  203.     or    dx,dx            ; test sign of 32 bit value,
  204.     pushf                ; and save sign on stack.
  205.     jns    bin1            ; jump if it was positive.
  206.     not    dx            ; negative, take 2's complement
  207.     not    ax            ; of the value. 
  208.     add    ax,1
  209.     adc    dx,0
  210. bin1:                    ; divide 32 bit value by radix 
  211.                     ; to extract next digit for the
  212.                     ; forming string.
  213.     mov    bx,ax            ; is the value zero yet?
  214.     or    bx,dx
  215.     jz    bin3            ; yes, we are done converting.
  216.     call    divide            ; no, divide by radix.
  217.     add    bl,'0'            ; convert remainder to ASCII digit.
  218.     cmp    bl,'9'            ; might be converting to hex ASCII,
  219.     jle    bin2            ; jump if in range 0-9,
  220.     add    bl,'A'-'9'-1        ; correct it if in range A-F.
  221. bin2:    mov    [si],bl            ; store this character into string.
  222.     dec    si            ; back up through string,
  223.     jmp    bin1            ; and do it again.
  224. bin3:                    ; restore sign flag,
  225.     popf                ; was original value negative?
  226.     jns    bin4            ; no, jump
  227.     mov    byte ptr [si],'-'    ; yes,store sign into output.
  228. bin4:    ret                ; back to caller.
  229.  
  230. binasc    endp
  231.  
  232. ;
  233. ; General purpose 32 bit by 16 bit unsigned divide.
  234. ; This must be used instead of the plain machine unsigned divide
  235. ; for cases where the quotient may overflow 16 bits (for example,
  236. ; dividing 100,000 by 2).  If called with a zero divisor, this
  237. ; routine returns the dividend unchanged and gives no warning.
  238. ;
  239. ; Call with DX:AX = 32 bit dividend
  240. ;           CX    = divisor
  241. ;
  242. ; Returns   DX:AX = quotient
  243. ;           BX    = remainder
  244. ;        CX    = divisor (unchanged)
  245. ;
  246. divide    proc    near            ; Divide DX:AX by CX
  247.  
  248.     jcxz    div1            ; exit if divide by zero
  249.     push    ax            ; 0:dividend_upper/divisor
  250.     mov    ax,dx
  251.     xor    dx,dx
  252.     div    cx
  253.     mov    bx,ax            ; BX = quotient1
  254.     pop    ax            ; remainder1:dividend_lower/divisor
  255.     div    cx
  256.     xchg    bx,dx            ; DX:AX = quotient1:quotient2
  257.  
  258. div1:    ret                ; BX = remainder2
  259.  
  260. divide    endp
  261.  
  262.  
  263.  
  264. pmsg    proc    near            ; print a message on std output
  265.                     ; call with DS:EDX = address 
  266.                     ;           ECX    = length 
  267.     mov    ah,40h
  268.     mov    bx,stdout
  269.     int    21h
  270.     ret
  271.  
  272. pmsg    endp
  273.  
  274.  
  275. _TEXT    ends
  276.  
  277.  
  278. _DATA    segment para public 'DATA'
  279.  
  280. flags    db      asize+1 dup (?)
  281. counter    dw      ?
  282.  
  283. msg1    db    cr,lf,'Starting '
  284. msg1a    db    '     iterations of Sieve...',cr,lf
  285. msg1_len equ $-msg1
  286.  
  287. msg2    db    cr,lf,'Primes found:  '
  288. msg2a    db    '     ',cr,lf
  289. msg2_len equ $-msg2
  290.  
  291. msg3    db    cr,lf,'Elapsed time:  '
  292. msg3a    db    '       msec. per iteration',cr,lf
  293. msg3_len equ $-msg3
  294.  
  295. _DATA    ends
  296.  
  297.  
  298. _STACK    segment byte stack 'stack'
  299.     db      4096 dup (?)
  300. _STACK    ends
  301.  
  302.     end    sieve
  303.